package cn.itcast.com.homework.day821;

import cn.itcast.com.Tree.MyTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by 郭浩 on 2020/8/21 19:53
 *
 3. 给定一棵二叉搜索树，它的根结点为root。求这棵树中不同结点的最小差值。
 public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode(int x) { val = x; }
 }
 比如：
 4
 /   \
 2      6
 / \
 1   3
 这棵树中，最小差值为1. (2结点和1结点，3结点和2结点)
 实现这个方法：public int minDiffInBST(TreeNode root) ；
 */

public class test2 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(4);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(6);
        TreeNode t4 = new TreeNode(1);
        TreeNode t5 = new TreeNode(3);

        t1.right = t3;
        t1.left = t2;
        t2.left = t4;
        t2.right = t5;
        int i = minDiffInBST(t1);
        System.out.println(i);

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    //广度优先搜索一层一层的遍历
    //和层次遍历类似
    public static int minDiffInBST(TreeNode root){
        int min = Integer.MAX_VALUE;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (poll.left != null){
                int abs_left = Math.abs(poll.left.val - poll.val);
                if (abs_left < min){
                    min = abs_left;
                }
                queue.offer(poll.left);
            }
            if (poll.right != null){
                int abs_right = Math.abs(poll.right.val - poll.val);
                if (abs_right < min){
                    min = abs_right;
                }
                queue.offer(poll.right);
            }
        }
        return min;
    }
}
